package algorithm.leetcode.I1to100;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 常规的组合回溯
 */

public class Q40 {

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> global = new LinkedList<>();
        // 去重手法1/2
        Arrays.sort(candidates);
        dfs(global, candidates, new LinkedList<>(), 0, target);
        return global;
    }

    private void dfs(List<List<Integer>> globalRes,
                     int[] candidates,
                     LinkedList<Integer> curr,
                     int start,
                     int left) {

        if (left <= 0 || start >= candidates.length) {
            if (left == 0) globalRes.add(new LinkedList<>(curr));
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            // 去重手法2/2,语法糖
            if (i == start || candidates[i] > candidates[i-1]) {
                curr.addLast(candidates[i]);
                dfs(globalRes, candidates, curr, i+1, left-candidates[i]);
                curr.removeLast();
            }
        }

    }

}
